<div class="problemindexholder" problemindex="B">
 <div class="ttypography">
  <div class="problem-statement">
   <div class="header">
    <div class="title">
     B. Polycarp's phone book
    </div>
    <div class="time-limit">
     <div class="property-title">
      time limit per test
     </div>
     4 seconds
    </div>
    <div class="memory-limit">
     <div class="property-title">
      memory limit per test
     </div>
     256 megabytes
    </div>
    <div class="input-file">
     <div class="property-title">
      input
     </div>
     standard input
    </div>
    <div class="output-file">
     <div class="property-title">
      output
     </div>
     standard output
    </div>
   </div>
   <div>
    <p>
     There are
     <span class="tex-span">
      <i>
       n
      </i>
     </span>
     phone numbers in Polycarp's contacts on his phone. Each number is a 9-digit integer, starting with a digit different from
     <span class="tex-span">
      0
     </span>
     . All the numbers are distinct.
    </p>
    <p>
     There is the latest version of Berdroid OS installed on Polycarp's phone. If some number is entered, is shows up all the numbers in the contacts for which there is a substring equal to the entered sequence of digits. For example, is there are three phone numbers in Polycarp's contacts:
     <span class="tex-span">
      123456789
     </span>
     ,
     <span class="tex-span">
      100000000
     </span>
     and
     <span class="tex-span">
      100123456
     </span>
     , then:
    </p>
    <ul>
     <li>
      if he enters
      <span class="tex-span">
       00
      </span>
      two numbers will show up:
      <span class="tex-span">
       100000000
      </span>
      and
      <span class="tex-span">
       100123456
      </span>
      ,
     </li>
     <li>
      if he enters
      <span class="tex-span">
       123
      </span>
      two numbers will show up
      <span class="tex-span">
       123456789
      </span>
      and
      <span class="tex-span">
       100123456
      </span>
      ,
     </li>
     <li>
      if he enters
      <span class="tex-span">
       01
      </span>
      there will be only one number
      <span class="tex-span">
       100123456
      </span>
      .
     </li>
    </ul>
    <p>
     For each of the phone numbers in Polycarp's contacts, find the minimum in length sequence of digits such that if Polycarp enters this sequence, Berdroid shows this only phone number.
    </p>
   </div>
   <div class="input-specification">
    <div class="section-title">
     Input
    </div>
    <p>
     The first line contains single integer
     <span class="tex-span">
      <i>
       n
      </i>
     </span>
     (
     <span class="tex-span">
      1 ≤
      <i>
       n
      </i>
      ≤ 70000
     </span>
     ) — the total number of phone contacts in Polycarp's contacts.
    </p>
    <p>
     The phone numbers follow, one in each line. Each number is a positive 9-digit integer starting with a digit from
     <span class="tex-span">
      1
     </span>
     to
     <span class="tex-span">
      9
     </span>
     . All the numbers are distinct.
    </p>
   </div>
   <div class="output-specification">
    <div class="section-title">
     Output
    </div>
    <p>
     Print exactly
     <span class="tex-span">
      <i>
       n
      </i>
     </span>
     lines: the
     <span class="tex-span">
      <i>
       i
      </i>
     </span>
     -th of them should contain the shortest non-empty sequence of digits, such that if Polycarp enters it, the Berdroid OS shows up only the
     <span class="tex-span">
      <i>
       i
      </i>
     </span>
     -th number from the contacts. If there are several such sequences, print any of them.
    </p>
   </div>
   <div class="sample-tests">
    <div class="section-title">
     Examples
    </div>
    <div class="sample-test">
     <div class="input">
      <div class="title">
       Input
      </div>
      <pre>3<br/>123456789<br/>100000000<br/>100123456<br/></pre>
     </div>
     <div class="output">
      <div class="title">
       Output
      </div>
      <pre>9<br/>000<br/>01<br/></pre>
     </div>
     <div class="input">
      <div class="title">
       Input
      </div>
      <pre>4<br/>123456789<br/>193456789<br/>134567819<br/>934567891<br/></pre>
     </div>
     <div class="output">
      <div class="title">
       Output
      </div>
      <pre>2<br/>193<br/>81<br/>91<br/></pre>
     </div>
    </div>
   </div>
  </div>
  <p>
  </p>
 </div>
</div>
